package me.mingshan.leetcode;

/**
 * @author hanjuntao
 * @date 2025/10/2 0002
 */
public class L_110_平衡二叉树 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(9);
        TreeNode node2 = new TreeNode(20);
        TreeNode node3 = new TreeNode(15);
        TreeNode node4 = new TreeNode(7);
        root.left = node1;
        root.right = node2;
        node2.left = node3;
        node2.right = node4;
        TreeNode.print(root);
        System.out.println(isBalanced(root));
    }

    /**
     * 判断是否是平衡二叉树
     *
     * 平衡二叉树定义：任何树的左右子树的高度差不能超过1
     *
     * 递归实现:(采用自上而下)
     *
     * 递归调用，判断左右子树是否平衡，并且左右子树的高度差不能超过1
     *
     * 这种方式涉及到重复计算，效率较低
     * 时间复杂度：O(n^2)
     *
     *
     * @param root
     * @return
     */
    public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        TreeNode left = root.left;
        TreeNode right = root.right;

        int leftDepth = maxDepth(left);
        int rightDepth = maxDepth(right);
        return Math.abs(leftDepth - rightDepth) <= 1 && isBalanced(left) && isBalanced(right);
    }

    private static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    public boolean isBalanced2(TreeNode root) {
        return getHeight(root) != -1;
    }

    /**
     * 递归实现:(采用自下而上)
     *
     * 获取树的高度，如果树平衡，则返回树的高度，否则返回-1
     *
     * @param root 树根节点
     * @return 树高度， -1表示树不平衡
     */
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }

        // 左右子树的高度差不能超过1，否则返回-1
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        // 返回树的高度
        return Math.max(leftHeight, rightHeight) + 1;
    }


}
